public class BestTime2BuyAndSellStock {
    /**
     * 121. 买卖股票的最佳时机
     *
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     *
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     *
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     *
     * 示例 1：
     *
     * 输入：[7,1,5,3,6,4]
     * 输出：5
     * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     *      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     * 示例 2：
     *
     * 输入：prices = [7,6,4,3,1]
     * 输出：0
     * 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
     *
     * 提示：
     *
     * 1 <= prices.length <= 10^5
     * 0 <= prices[i] <= 10^4
     */

    public static void main(String[] args) {

    }

    /**
     * 动态规划
     * 1.明确dp数组及下标含义。首先i一定是天数，其次，每天都一定只有两种状态：持股 或 不持股，这两种状态都需要使用，不能重叠，因此是dp[i][0] dp[i][1]
     *    分别表示第i天持股、不持股能获得的最大金额
     *
     * 2.递推公式。第i天的两个值均依赖前一天的状态：
     *      持股：前一天就持股，或者刚好这一天买入
     *      不持股：前一天不持股，或者前一天持股，刚好今天卖出
     *   故：dp[i][0] = max(dp[i-1][0], -prices[i])
     *      dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0])
     *
     * 3.dp数组初始化：
     *      第一天持股，即第一天就买入：dp[0][0] = -prices[0]
     *      第一天不持股： dp[0][1] = 0
     */
    public int mySolution(int[] prices) {
        int[] dp = new int[2];
        dp[0] = -prices[0];
        dp[1] = 0;

        for (int i = 1; i < prices.length; i++){
            // 注意，这里dp[1]依赖昨天的dp[0], 因此要先计算dp[1], 避免昨天的数据被覆盖
            dp[1] = Math.max(dp[1], prices[i] + dp[0]);
            dp[0] = Math.max(dp[0], -prices[i]);
        }

        // 不持股一定比持股金额大，因为持股意味着买了没卖
        return dp[1];
    }

    // 可以用贪心，除非数组递减，股票一定是在最小的时候买入，取最左最小值就好
    public int greedy(int[] prices){
        int lowest = Integer.MAX_VALUE;
        int result = 0;
        for (int i : prices){
            // 总是保证lowest最小
            lowest = Math.min(lowest, i);
            result = Math.max(result, i - lowest);
        }
        return result;
    }
}
